/*
 * function diff(o,n)
 *	By John Resig (http://ejohn.org/)
 *	Modified by Chu Alan "sprite"
 *	CC-BY-2.5 http://creativecommons.org/licenses/by/2.5/
 *	http://ejohn.org/projects/javascript-diff-algorithm/
 *
 * Remainder of file: Conrad Irwin, see COPYRIGHT
 *
 */

/*** TODO ***
 * 
 * Minimise diffs (i.e. move the start up and the end down until an actual character difference)
 *
 * Work out how to describe what caused a diff to fail to be applied
 *
 * Test creating stable change messages (currently 98% sure)
 * Test finding changes without conflicts (currently 85% sure)
 * Test on realer data
 *
 * Tune heuristics!
 * Check more
 */

/**
 * Object description:
 *
 * a diff is an array of blocks ordered by starting position.
 *
 * a block is an object with
 *  starting position  s:number
 *  ending position  e:number
 *  an array of changes ordered by starting position  c:Array<change>
 *  the position in which it occurs in the new document  p:number
 *   (the first step in applying the diff is to move the blocks in the correct order)
 *
 * a change is an object with
 *  starting position  s:number
 *  ending position  e:number
 *  the inserted text  i:string
 *   (All text between s and e is replaced by i)
 *
 * in order to "stabalise" blocks and changes to create
 * stable_blocks and stable_changes
 * context parameters are added
 *  text before starting position  bs:string
 *  text after starting position  as:string
 *  text before ending position  be:string
 *  text after ending position  ae:string
 *
 * a heckel_diff is an object with
 *  An ordered array of symbols from the old document  o:Array<symbol>
 *  An ordered array of symbols in the new document  n:Array<symbol>
 *
 * a symbol is either a string,
 *  (which in heckel_diff.o indicates deleted text
 *   which in heckel_diff.n indicates inserted text)
 * or an object with
 *  the contents of the symbol  text:string
 *  the position in the other array that this symbol appears  row:number
 *   (if heckel_diff.o[i].row == j, heckel_diff.n[j].row == i)
 *
 * a patch_handler is an object with
 *  a function to alert the user of a diff with unfindable blocks diffError:function<diff>
 *  a function to alert the user to a block with no findable changes blockError:function<block>
 *  a function to alert the user to an unfindable change changeError:function<change>
 */

/**
 * A namespace for diff-taking functions.
 */
window.Diff = {
/** DIFF **/

	/**
	 * Generate a "stable diff" from two documents.
	 *
	 * If you were to patch the return value of this function with
	 * a document that was similar enough to the first parameter
	 * you would get a document that resembled the second parameter.
	 * 
	 * (public)
	 * @param {string} o  The old document
	 * @param {string} n  The new document
	 * @return {stable_diff}  The differences between the two
	 */
	stableDiff: function (o,n)
	{
		/* TODO: Some optimisation is possible here -
		 *       it might be nice to update our "stable diff" definition to
		 *       allow sending the bit between start and end instead of a fixed
		 *       amount before and after each. 
		 *
		 *       It might be quicker to merge this function with exactDiff so
		 *       that one pass through the string can be avoided
		 */
		blocks = this.exactDiff(o, n);
	
		for (var i=0; i < blocks.length; i++)
		{
			b = this.stableRange(blocks[i], o);
			for (var j=0; j < b.c.length; j++)
			{
				var context = o.substr(b.s, b.e-b.s);
				b.c[j] = this.stableRange(this.minimiseChange(b.c[j], context), context);
			}
			blocks[i] = b;
		}
	
		return blocks;
	},

	/**
	 * Generate a "diff" from two documents.
	 *
	 * If you were to patch the return value of this function
	 * with the first parameter, you would get the second parameter.
	 * Generally you will want to call stableDiff. Not this function
	 *
	 * (public)
	 * @param {string} o the old document
	 * @param {string} n the new document
	 * @return {diff}  the difference between the two
	 */
	exactDiff: function (o, n)
	{
		//Split the text at the start of each word (without absorbing split char) 
		// The actual split doesn't make any difference apart from efficiency
		//
		// Note that this split gives space as "leading" except for the first word
		// which has no space.
		//
		// If considering different splits, it is important to ensure that you get
		// a reasonable number of items that appear exactly once in each list. So that
                // the algorithm can propogate links from these. It is also important to 
                // ensure you get a reasonable length of term - even in multiple character sets.
                // (I got bitten by the fact that \w may not recognise chars in non-latin alphabets)
		//
		// "one two three" => ["one", " two", " three"]
		var out = this.heckelDiff(o.split(/(?=\s\S)/), n.split(/(?=\s\S)/));
		var news = out.n;
		var olds = out.o;

		var blocks = Array();
		var starts = {};

		var startpos = 0; //The position of the start of the block
		var startrow = 0;   //The row in the "new" document that a block starts in.

		var changes = Array(); //Any replacements that happen in this block

		var oldlen = olds.length;
		var newlen = news.length;

		var predeleted = '';
		var preinserted = '';

		var i = 0; //The position in the symbol table of the original document
		var j = 0; //The position in the symbol list of the new document

		//Skip over any initial deletes until we find the first symbol that
		//appears in both documents.
		while (i < oldlen && olds[i].text == null) {
			predeleted += olds[i];
			i++;
		}

		//Record any innitial inserts to be added as a change to the first block
		//in the new document (may != first block in the old document)
		while (j < newlen && news[j].text == null) {
			preinserted += news[j];
			j++;
		}

		var curpos = predeleted.length;	//The char offset from the start of the file.

		while (i < oldlen)
		{
			//Initialise block loop
			startpos = curpos;
			j = startrow = olds[i].row;
			changes = Array ();

			//While we are in the same block, keep recording changes.
			// It might give a small advantage in size to separate insert and delete
			// but it's easier on the merger if it only has one "replace" operation
			// to think about.
			do
			{
				curpos += olds[i].text.length;
				i++;
				j++;

				var deleted = '';
				var inserted = '';

				//What has been deleted
				while (i < oldlen && olds[i].text == null)
				{
					deleted += olds[i];
					i++;
				}

				//What has been inserted
				while (j < newlen && news[j].text == null)
				{
					inserted += news[j];
					j++;
				}
				
				//If anything has changed, record it.
				// It doesn't matter how much was inserted as we
				// don't need to keep track of exact position in the new document
				if (deleted + inserted != "")
				{
					changes.push({s:curpos-startpos, e: curpos+deleted.length-startpos, i: inserted});
					curpos += deleted.length;
				}

			} while (j < newlen && news[j].row == i)

			blocks.push({s: startpos, e: curpos, c: changes});
			starts[startrow] = blocks[blocks.length - 1];
		}

		if (blocks.length) {

			//Add a position parameter so we know what order they appear
			//in the new document
			var sts = Array();
			for (st in starts)
				  sts.push(st);
			sts.sort();
			for (var i=0; i < sts.length; i++)
			{
				 starts[sts[i]].p = i;
			}
					
			var first_n = starts[sts[0]];
			var first_o = blocks[0];

			//Add the inserts and deletes from the start into the changeset
			if (first_o == first_n && predeleted+preinserted != '')
			{
				for (var i=0; i< first_o.c.length; i++)
				{
					first_o.c[i].s += first_o.s;
					first_o.c[i].e += first_o.s;
				}
				first_o.c.unshift({s: 0, e: predeleted.length, i: preinserted});
				first_o.s = 0;
			} else {
				if (preinserted != '') {
					first_n.c.unshift({s: 0, e: 0, i: preinserted});
				}
				if (predeleted != '') {
					//Add the delete change to the first block
					//and ensure that all changes have their positions
					//updated to reflect this.
					for (var i=0; i< first_o.c.length; i++)
					{
						first_o.c[i].s += first_o.s;
						first_o.c[i].e += first_o.s;
					}
					first_o.c.unshift({s: 0, e: predeleted.length, i: ''});
					first_o.s = 0;
				}
			}

			return blocks;

		} else { //No words in common, the entire document has been deleted/inserted
			blocks.push({s: 0, e: o.length, c: [], p: 0});
			if(predeleted+preinserted != "")
				blocks[0].c.push({s: 0, e: predeleted.length, i: preinserted});
			return blocks;
		}
	},

	/**
	 * Add context parameters to an object.
	 *
	 * NB: this modifies the object passed in directly.
	 *
	 * (private)
	 * @param {change|block} obj  The object to add context to
	 * @param {string} str  The string to get the context from
	 * @return {stable_change|stable_block}   The object that was passed in
	 */
	stableRange: function (obj, str)
	{
		var length = 10;

		//Before start
		if (obj.s < length)
			obj.bs = str.substr(0, obj.s);
		else
			obj.bs = str.substr(obj.s-length, length);

		//After start
		obj.as = str.substr(obj.s, length);

		//Before end
		if (obj.e < length)
			obj.be = str.substr(0, obj.e);
		else
			obj.be = str.substr(obj.e-length, length);

		//After end
		obj.ae = str.substr(obj.e, length);
		return obj;
	},

	/**
	 * Remove anything that has not changed from the change.
	 *
	 * NB: this is not essential, just makes highlighting nicer.
	 *
	 * (private)
	 * @param {change} change  The change to minimise
	 * @param {string} str  The string from which the change comes
	 * @return {change} change  The change with start and end points
	 *							possibly moved closer together.
	 */
	minimiseChange: function (change, str)
	{
		var i=0;
		while (i < change.i.length && str.charAt(change.s + i) == change.i.charAt(i))
			i++;

		var j=0;
		while (j < change.i.length + i && str.charAt(change.e - j) == change.i.charAt(change.i.length - (j+1)))
			j++;

		change.s += i;
		change.e -= j;
		change.i = change.i.substr(i, change.i.length - j - i);
		return change;
	},

	/**
	 * get the "heckel_diff" from two arrays
	 *
	 * Uses the algorithm in Heckel 78 but on array
	 * items instead of lines.
	 *
	 * example of links created: S(tart block) E(nd block) I(nsert) D(elete)
	 * S a\  f SI
	 *   b\\ g I
	 * D c \\a
	 * D d  \b
	 *   e - e
	 * D h  /j I
	 * D i / m I
	 * E j/  n E
	 * S k\ /l S
	 * E o X p EI
	 * S l/ \k S
	 *
	 * (private)
	 * @param {Array} o  The array of original symbols
	 * @param {Array} n  The array of new symbols
	 * @return {heckel_diff}   The differences between the two arrays
	 */
	heckelDiff: function ( o, n ) {
		var ns = new Object();
		var os = new Object();
		
		/* pass one: 
		 *		each item of N is read in sequence
		 *		ns[item] is created, if it doesn't exist 
		 *		insert the position of the item into ns[item].rows
		 */
		for ( var i = 0; i < n.length; i++ ) {
			if ( ns[ n[i] ] == null )
				ns[ n[i] ] = { rows: new Array(), o: null };
			ns[ n[i] ].rows.push( i );
		}
		
		/* pass two:
		 *		each item of O is read in sequence
		 *		os[item] is created, if it doesn't exist
		 *		insert the position of the item into os[item].rows
		 */
		for ( var i = 0; i < o.length; i++ ) {
			if ( os[ o[i] ] == null )
				os[ o[i] ] = { rows: new Array(), n: null };
			os[ o[i] ].rows.push( i );
		}

		/* pass three:
		 *		for each item that appears excatly once in the N array
		 *		and which appears exactly once in the O array
		 *		Make the two single occurances point to each other
		 *
		 *		Converts n[i]/o[i] from "text" to {text: "text", row: 9}
		 *
		 *		This is to indicate lines that probably haven't been changed,
		 *		just moved.
		 */
		for ( var i in ns ) {
			if ( ns[i].rows.length == 1 && typeof(os[i]) != "undefined" && os[i].rows.length == 1 ) {
				n[ ns[i].rows[0] ] = { text: n[ ns[i].rows[0] ], row: os[i].rows[0] };
				o[ os[i].rows[0] ] = { text: o[ os[i].rows[0] ], row: ns[i].rows[0] };
			}
		}
		
		/**
		 * pass four:
		 *		Go through in ascending order and 
		 *		If a line in NS points to a line in OS, and the next
		 *		item in each line is the same, assume that those lines
		 *		also haven't changed at create a link between the next
		 *		NS and OS pairs.
		 *
		 *		If .text == null, then there is no link between n and o,
		 *		as when the link is created the value changes from a string into a {text:, row:} object.
		 */
		for ( var i = 0; i < n.length - 1; i++ ) {
			if ( n[i].text != null && n[i+1].text == null && n[i].row + 1 < o.length && o[ n[i].row + 1 ].text == null && 
					 n[i+1] == o[ n[i].row + 1 ] ) {
				n[i+1] = { text: n[i+1], row: n[i].row + 1 };
				o[n[i].row+1] = { text: o[n[i].row+1], row: i + 1 };
			}
		}

		/**
		 * pass five
		 *		Do pass four in reverse, propogating links to identical parts
		 *		backwards in the list.
		 */
		for ( var i = n.length - 1; i > 0; i-- ) {
			if ( n[i].text != null && n[i-1].text == null && n[i].row > 0 && o[ n[i].row - 1 ].text == null && 
					 n[i-1] == o[ n[i].row - 1 ] ) {
				n[i-1] = { text: n[i-1], row: n[i].row - 1 };
				o[n[i].row-1] = { text: o[n[i].row-1], row: i - 1 };
			}
		}
		
		return { o: o, n: n };
	},


/** PATCH **/

	/**
	 * Patch a stable_diff onto a document.
	 *
	 * The document may be slightly different from the one
	 * used to create the patch originally.
	 *
	 * NB. This function may modify it's input objects!
	 *
	 * (public)
	 * @param {diff} diff  The diff to apply
	 * @param {string} str  The document to apply it to
	 * @param {patch_handler}  handler  a set of callbacks for error handling. 
	 * @return {string|null}   The resulting document or null on error.
	 */
	stablePatch: function (diff, str, handler)
	{
		var blocks = this.findBlocks(diff, str, handler);

		if (blocks == null)
			return str;
		else
			return this.exactPatch(blocks, str);
	},
	
	/**
	 * Patch a diff onto a document.
	 *
	 * If the document is not identical to the document used to create the
	 * patch, then the result is undefined and probably ugly. Use stablePatch
	 * instead.
	 *
	 * (public)
	 * @param {diff} blocks  The diff to apply
	 * @param {string} str  The document to apply it to
	 * @return {string|null}   The resulting document or null if the diff is badly formed
	 */
	exactPatch: function (blocks, str)
	{
		var out = Array();

		var prevend = 0; //Merely for robustness - not needed in a perfect world

		for (var i=0; i<blocks.length; i++)
		{
			if (blocks[i].s != prevend) //Blocks must be contiguous
				return null
			prevend = blocks[i].e;
		
			//Apply changes to this block
			out[blocks[i].p] = this.applyChanges(blocks[i].c,str.substr(blocks[i].s, blocks[i].e - blocks[i].s))

			if (out[blocks[i].p] == null) //All changes must be successfullly applied
				return null;
		}

		if (prevend != str.length) //Blocks must encompass entire string
			return null;

		//Join together the blocks in the order they specify
		return out.join("");
	},

	/**
	 * Apply the given changes to a string.
	 *
	 * This is deisigned so that you can pass the contents of a block
	 * and the block's list of changes, and get the new contents of a block.
	 *
	 * (private)
	 * @param {Array<change>} changes  The changes to apply
	 * @param {string} str  The string to apply them to
	 * @return {string|null}   The resulting string or null on failure
	 */
	applyChanges: function (changes, str)
	{
		var offset = 0; //As each change is applied it may change the length of the string
						// the other changes will thus have to be applied in a different place
		for (var i = 0; i < changes.length; i++)
		{
			var change = changes[i];

			str = str.substr(0, change.s + offset) + change.i + str.substr(change.e + offset);
			offset += change.i.length - (change.e - change.s);
			
			//Someone gave us a dodgy diff. The changes are in order for a reason!
			if (changes[i+1] != null && changes[i+1].s < change.e)
				return null;
		}

		return str;
	},

	/**
	 * Find the likely block boundaries within the given string
	 * 
	 * (private)
	 * @param {Array<stable_block>} blocks  The blocks to search for (must be ordered correctly)
	 * @param {string} str  The string in which to search for them
         * @param {Object} handler  A handler which has error callbacks
         *                                .blockError, .diffError and .changeError
	 * @return {Array<block>|null}   The input with the .s and .e properties corrected
	 */
	findBlocks: function (blocks, str, handler)
	{
		var orig = Array();
		var poss = Array();

		var prevend = 0;
		
		//The first division is always the start of the string
		poss.push([0]);
		orig.push(blocks[0].s);

		//Find the possible positions of the other boundaries
		for (var i=0; i < blocks.length; i++)
		{
			poss.push(this.positionList(blocks[i].be + blocks[i].ae, str, blocks[i].be.length));
			orig.push(blocks[i].e);

			if (blocks[i].s != prevend)
			{
				handler.diffError(blocks);
				return null; //Blocks are not contiguous
			}

			prevend = blocks[i].e;

		}
		//Last block must end at end of string
		poss[poss.length-1] = [str.length]

		//Find the positions, maximum distance is str.length, minimum difference is 1/2 a percent
		var find = this.optimalPositions(orig, poss, str.length, str.length * 0.005);

		if (find == null)
		{
			handler.diffError(blocks);
			return null;
		}

		var newblocks = [];
		for (var i=0; i<blocks.length; i++)
		{
			var changes = this.findChanges(blocks[i].c, str.substr(find[i], find[i+1] - find[i]), handler)
			if (changes == null)
			{
				handler.blockError(blocks[i]);
				changes = [];
			}
			newblocks.push({
				s: find[i],
				e: find[i+1],
				c: changes,
				p: blocks[i].p
			});
		}

		return newblocks;
	},
	
	/**
	 * Find the likely position of changes within the given string.
	 *
	 * This may deleted changes that it detects have "already happened" in the new string,
	 * so that if two users make the same change it won't conflict.
	 *
	 * (private)
	 * @param {Array<stable_change>} changes  The changes to find (must be ordered correctly)
	 * @param {string} str  The string in which to search for them
	 * @param {patch_handler} handler  The error handler.
	 * @return {Array<change>}   The input asrray with .s and .e properties updated.
	 */
	findChanges: function (ochanges, str, handler)
	{
		var orig = Array();
		var poss = Array();

		//Get round the fact that this function modifies its input - FIXME properly
		var changes = Array();
		for (var i=0; i< ochanges.length; i++)
			changes.push(ochanges[i]);

		var prevend = 0;

		//Tie to the start of the string
		orig.push(0);
		poss.push([0]);

		for (var i=0; i < changes.length; i++)
		{
			poss.push(this.positionList(changes[i].bs + changes[i].as, str, changes[i].bs.length));
			orig.push(changes[i].s);

			poss.push(this.positionList(changes[i].be + changes[i].ae, str, changes[i].be.length));
			orig.push(changes[i].e);

			//Hrm, there were no places that the string could have been inserted.
			// Probably indicates a conflict
			if (poss[poss.length -1].length == 0 || poss[poss.length -2].length == 0)
			{
				//Let's be optimistic and see if the change may have already been applied
				var applied = this.positionList(changes[i].bs + changes[i].i + changes[i].ae, str, 0);

				//Nope, it was a duff one
				if (applied.length == 0)
					handler.changeError(changes[i]);

				//Remove this change
				poss.splice(poss.length-2,2);
				orig.splice(orig.length-2,2);
				changes.splice(i--,1);

			}
			else
			{

				if (changes[i].s < prevend)
					return null; //Changes are not ordered.

				prevend = changes[i].e;
			}
		}

		//Tie to end of string
		orig.push(str.length);
		poss.push([str.length]);

		var find = this.optimalPositions(orig, poss, str.length, str.length * 0.005);

		if (find == null)
			return null;

		var newchanges = [];
		for (var i=0; i < changes.length; i++)
		{
			newchanges[i] = {
				s: find[2*i+1],
				e: find[2*i+2],
				i: changes[i].i
			}
		}

		return newchanges;
	},

	/**
	 * Find all the occurances of the context in the string.
	 *
	 * By specifying prefix_length, the positions returned can be offset
	 * to return something more useful than the start of the match.
	 *
	 * @param {string} context  The string to search for
	 * @param {string} str  The string to seach in
	 * @param {number} prefix_length  The amount to add to each position in the result
	 * @return {Array<number>}   The positions found.
	 */
	positionList: function (context, str, prefix_length) {
		var out = Array();
		if (context == "") { //Nasty edge case that causes infinite loops
			if (str == "") out.push(0)
			return out;
		}
		var i = str.indexOf(context);
		while (i != -1) 
		{
			out.push(i + prefix_length);
			i = str.indexOf(context, i+1);
		}
		return out;
	},

	/**
	 * Get the most likely list of positions.
	 *
	 * Does a naive "shortest path" algorithm, where the change in
	 * distance between two points is minimised. If no good path can 
	 * be found, null is returned.
	 *
	 * @param {Array<number>} orig  The original positions
	 * @param {Array<Array<number>>} poss  The possible new positions
	 * @param {number} looseness  The maximum distance between the original path
	 *                          and the best possible path before it is considered
	 *                          to have failed.
	 * @param {number} equal  (optional) If the two best possible paths are within
	 *                                 this distance of each other, then the match
	 *                                 fails as no possibility is clearly correct.
	 * @return {Array<number>}   The most probable positions
	 */
	optimalPositions: function (orig, poss, looseness, equal)
	{
		//At this point we have a list of possible places each can be
		//and a list of original points.
		//
		//Now to match them up s that the difference between each item 
		//in each list is most similar
		//
		// [                
		//  [0],           [0,        [0     +1
		//  [4,6],          5,         6,    +0
		//  [9],      +     8,   =     9.    +0
		//  [13,19],        12,        13,   +0
		//  [20]            19]        20]
		// ]
		var find = Array();

		if (orig.length != poss.length ||
			(poss.length < 2) ||
			(poss[0].length != 1) ||
			(poss[poss.length-1].length != 1)) 
			return null; //Bad function arguments. (for robustness only)

		//The last division is always the end of the string
		var i=0;
		while (i < poss.length)
		{
			if (poss[i].length == 1)
			{
				find[i] = poss[i][0];
				i++;
			}
			else if (poss[i].length == 0)
			{
				return null; //Change could not be found
			}
			else 
			{
				// A naive search for the "best" insert position
				//
				// Declared as an inline function as we want to keep the
				// scope.
				//
				// While we could run this on the whole thing to find the
				// correct positions it is more efficient to only run it
				// when there is choice as it is O(mn^2) whereas the normal
				// loop is O(n).
				function find_path (prev_pos, j)
				{
					var ideal = prev_pos + orig[j] - orig[j-1];

					//optimisation to reduce length of n - waiting until last j
					//  would work fine
					if (poss[j].length == 1)
					{
						return [[poss[j][0]], Math.abs(poss[j][0] - ideal)];
					}
					else if (poss[j].length == 0)
					{
						return null; //Change couldn't be found
					}
					else
					{
						var best = null;
						for (var k=0; k < poss[j].length; k++)
						{
							var sol = find_path(poss[j][k], j+1);
							sol[1] += Math.abs(poss[j][k] - ideal)
							if (sol[0] != null)
								sol[0].unshift(poss[j][k]);

							//Invalidate any solutions that are too similar
							if (equal != null && best != null && Math.abs(sol[1] - best[1]) < equal)
								sol[0] = null;

							if (!best || sol[1] < best[1])
								best = sol;

						}

						return best;
					}
				}
				var res = find_path(orig[i-1], i);

				if (res == null || (looseness != null && res[1] > looseness))
					return null; //Don't apply patch if no good insert position

				if (res[0] == null)
					return null; //Don't apply patches if two insertion points were equal

				//Add the newly found best path to the output
				for (var k=0; k < res[0].length; k++)
				{
					find[i++] = res[0][k];
				}
			}
		}
		return find;
	},

/** UTIL **/

	/**
	 * Does the diff make no difference?
	 *
	 * @param {diff} diff the diff to analyze
	 * @return {boolean} true if the diff makes no difference.
	 */
	isNull: function  (diff)
	{
		var nochange = true
		var curr_p = 0;
		for (var i=0; i<diff.length; i++)
		{
			if (diff[i].c.length > 0)
			{
				nochange = false;
			}
			if (diff[i].p != curr_p)
			{
				nochange = false;
			}

			curr_p++;
		}

		return nochange;
	},

	/**
	 * Are the diffs the same?
	 *
	 * Checks to see if the diffs are the same. This is not
	 * the same as checking if they make the same changes!
	 *
	 * @param {diff} diff1
	 * @param {diff} diff2
	 */
	isEqual: function (diff1, diff2)
	{
		if (diff1.length != diff2.length)
			return false;

		for (var i=0; i < diff1.length; i++)
		{
			if (! (diff1[i].s == diff2[i].s &&
				   diff1[i].e == diff2[i].e &&
				   diff1[i].p == diff2[i].p &&
				   diff1[i].c.length == diff2[i].c.length))
				return false;

			for (var j=0; j < diff1[i].c.length; j++)
			{
				if (! (diff1[i].c[j].s == diff2[i].c[j].s &&
					   diff1[i].c[j].e == diff2[i].c[j].e &&
					   diff1[i].c[j].i == diff2[i].c[j].i
					  ))
					return false;
			}
		}
		return true;
	}

};

